package leetcode.editor.cn;

/**
 * @Author: Dempsey
 * @Data: 2021-01-08 20:12:08
 */

//给你两个二进制字符串，返回它们的和（用二进制表示）。 
//
// 输入为 非空 字符串且只包含数字 1 和 0。 
//
// 
//
// 示例 1: 
//
// 输入: a = "11", b = "1"
//输出: "100" 
//
// 示例 2: 
//
// 输入: a = "1010", b = "1011"
//输出: "10101" 
//
// 
//
// 提示： 
//
// 
// 每个字符串仅由字符 '0' 或 '1' 组成。 
// 1 <= a.length, b.length <= 10^4 
// 字符串如果不是 "0" ，就都不含前导零。 
// 
// Related Topics 数学 字符串 
// 👍 538 👎 0


public class P67 {
    public static void main(String[] args) {
        Solution solution = new P67().new Solution();
        String a = "11";
        String b = "0";
        solution.addBinary(a, b);
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public String addBinary(String a, String b) {
            StringBuilder ans = new StringBuilder();
            StringBuilder sb_a = new StringBuilder(a).reverse();
            StringBuilder sb_b = new StringBuilder(b).reverse();

            int more = sb_a.length() - sb_b.length();
            if (more > 0) {
                while (more > 0) {
                    more--;
                    sb_b.append("0");
                }
            }
            if (more < 0) {
                more = -more;
                while (more > 0) {
                    more--;
                    sb_a.append("0");
                }
            }

            int carry = 0;

            for (int i = 0; i < sb_a.length(); i++) {
                int c = sb_a.charAt(i) + sb_b.charAt(i) + carry - 2 * '0';
                carry = c / 2;
                ans.append(c % 2);
            }

            ans.append(carry > 0 ? carry : "");

            return ans.reverse().toString();
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}